The present invention generally relates to electronic circuit design. More particularly, the present invention is directed to efficiently and accurately finding predetermined patterns in a main circuit design.
Recognizing or finding subcircuit instances in a larger circuit is widely used in the simulation, verification, and testing of integrated circuits using computer-aided design programs. Currently, the process of finding is performed using ad hoc techniques that rely on the circuit technology and implementation details. Such techniques, however, do not generalize to different subcircuit structures and do not transfer to other technologies. A publication entitled “SubGemini: Identifying SubCircuits using a Fast subgraph Isomorphism Algorithm,” by Ohlrich, et. al. (hereinafter “SubGemini”) describes a technology independent algorithm for solving this problem based on a solution to the subgraph isomorphism problem. This publication is incorporated herein by reference. SubGemini describes a use of a recursive relabeling approach to identify circuit patterns in a larger circuit. However, the SubGemini method of finding patterns in a larger circuit discards much of the information available in the labeling data, resulting in substantial inefficiencies.
Thus, there is a need for method and system that enable a more accurate and efficient identification of patterns (i.e., subcircuits) in a larger circuit.